package pers.qianyu.month_202012.date_20201225.dp_bag;

import pers.qianyu.util.*;

/**
 * 562. 背包问题 IV
 * https://www.lintcode.com/problem/backpack-iv/description
 * <strong>完全背包求种类数问题</strong>
 *
 * @author mizzle rain
 * @date 2020-12-25 15:03
 */
public class BackPackIV {
    /**
     * @param nums:   an integer array and all positive numbers, no duplicates
     * @param target: An integer
     * @return: An integer
     */
    public int backPackIV(int[] nums, int target) {
        int[] dp = new int[target + 1];
        dp[0] = 1;
        for (int num : nums) {
            for (int j = num; j <= target; j++) {
                dp[j] += dp[j - num];
            }
            ArrayUtil.printArrayAsMarkdownTable(num, dp);
        }
        return dp[target];
    }

    public static void main(String[] args) {
        int result = new BackPackIV().backPackIV(new int[]{2, 3, 6, 7}, 7);
        System.out.println("result = " + result);
    }
}
